/*************************************************************************
	> File Name: 002.unstable_sort.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 一  9/27 18:17:17 2021
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define COLOR(msg, code) "\033[0;" #code "m" msg "\033[0m"
#define YELLOW(msg)  COLOR(msg, 33)

#define swap(a, b) {\
    __typeof(a) _temp = a;\
    a = b;\
    b = _temp;\
}

#define TEST(arr, n, func, args...) {\
    int *nums = (int *)malloc(sizeof(int) * n);\
    memcpy(nums, arr, sizeof(int) * n);\
    output(nums, n);\
    printf("\n%s = ", #func);\
    long long begin = clock();\
    func(args);\
    long long end = clock();\
    output(nums, n);\
    printf(YELLOW("(%lld ms)") "\n", (end - begin) * 1000 / CLOCKS_PER_SEC);\
    free(nums);\
}


/*
 * 选择排序
 */
void selected_sort(int *arr, int n) {
    for (int i = 0; i < n - 1; i++) { //排序进行的趟数n-1
        int ind = i;
        for (int j = i + 1; j < n; j++) { //找到「待排序区」的最小值
            if (arr[ind] > arr[j]) ind = j; 
        }
        swap(arr[ind], arr[i]);
    }
}

/*
 * 快速排序
 */
void quick_sort(int *arr, int left, int right) {
    if (left > right) return ;
    int x = left, y = right, z = arr[x]; //z为基准值
    while (x < y) { //头尾指针未重合
        while (x < y && arr[y] > z) y--; //尾指针前移，找到比z小的值
        if (x < y) arr[x++] = arr[y]; //将尾指针指向的比z小的值放到头指针指向的位置
        while (x < y && arr[x] < z) x++; //头指针前移，找到比z大的值
        if (x < y) arr[y--] = arr[x]; //将头指针指向的比z大的值放到尾指针指向的位置
    }
    arr[x] = z; //放置基准值，数组基本有序，左边都比基准值小，右边都比基准值大
    quick_sort(arr, left, x - 1);//递归处理基准值左边部分
    quick_sort(arr, x + 1, right); //递归处理基准值右边部分
    return ;
}


void output(int *arr, int n) {
    printf("[");
    for (int i = 0; i < n; i++) {
        printf(" %d", arr[i]);
    }
    printf("]");
}

int main() {
    srand(time(0));
    #define max_op 20 
    int arr[max_op];
    for (int i = 0; i < max_op; i++) {
        arr[i] = rand() % 100;
    }
    TEST(arr, max_op, selected_sort, nums, max_op);
    TEST(arr, max_op, quick_sort, nums, 0, max_op - 1);

    #undef max_op
    return 0;
}
